package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_438_找到字符串中所有字母异位词 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_438_找到字符串中所有字母异位词().findAnagrams("cbaebabacd", "abc"));
        System.out.println(new 力扣_438_找到字符串中所有字母异位词().findAnagrams("abab", "ab"));
        System.out.println(new 力扣_438_找到字符串中所有字母异位词().findAnagrams("a", "c"));
        System.out.println(new 力扣_438_找到字符串中所有字母异位词().findAnagrams("baa", "aa"));
    }

    /**
    题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

     示例 1:
     输入: s = "cbaebabacd", p = "abc"
     输出: [0,6]
     解释:
     起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
     起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

     示例 2:
     输入: s = "abab", p = "ab"
     输出: [0,1,2]
     解释:
     起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
     起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
     起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

    分析：【P 💜💜💜】
       1.双指针+位图+相同字符数的统计： 位图记录26个字母：分别记录与目标字符串各个字符数的差距
                                        当26个字符的差距都为0时，此时满足异位词
                                        -- 执行用时：4 ms, 在所有 Java 提交中击败了98.28%的用户

    边界值 & 注意点：
       1.
     **/
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res =new ArrayList<>();
        if(p.length()>s.length())return res;
        int[] arr = new int[26];
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        for (char char1 : pArr) arr[char1 - 'a']--;//初始化位图
        for (int i = 0; i < pArr.length; i++) {
            arr[sArr[i] - 'a']++;
        }
        int left = 0,right=pArr.length-1,count=0;
        for (int anArr : arr) {//初始化相同字符串数：count值
            if (anArr == 0) count++;
        }
        if(count==26) res.add(left);
        while (++right<sArr.length){
            if(++arr[sArr[right]-'a']==0)
                count++;
            else if(arr[sArr[right]-'a']==1)
                count--;
            if(--arr[sArr[left]-'a']==0)
                count++;
            else if(arr[sArr[left]-'a']==-1)
                count--;
            left++;
            if(count==26) res.add(left);
        }
        return res;
    }
}
